package bin_tree.heap;

import java.util.*;

/**
 * 基于int的最大堆实现
 * 根节点从0开始编号
 * @author yuisama
 * @date 2022/01/05 19:46
 **/
public class MaxHeap {
    private List<Integer> data;

    public MaxHeap() {
        this(10);
    }

    public MaxHeap(int initCap) {
        this.data = new ArrayList<>(initCap);
    }

    /**
     * 将任意的整型数组调整为堆
     * heapify
     * @param arr
     */
    public MaxHeap(int[] arr) {
        // 1.先将arr所有元素拷贝到data中
        data = new ArrayList<>(arr.length);
        for (int i : arr) {
            data.add(i);
        }
        // 2.从最后一个非叶子节点开始进行元素下沉
        for (int i = parent(data.size() - 1); i >= 0; i--) {
            siftDown(i);
        }
    }

    public int peekHeap() {
        if (data.size() == 0) {
            throw new NoSuchElementException("heap is empty！");
        }
        return data.get(0);
    }

    /**
     * 将value存储在堆中。
     * @param value
     */
    public void add(int value) {
        // 在数组末尾添加元素
        this.data.add(value);
        // 进行元素上浮操作
        siftUp(data.size() - 1);
    }

    /**
     * 取出当前最大堆的最大值
     * @return
     */
    public int extractMax() {
        // 判断堆是否为空
        if (data.size() == 0) {
            throw new NoSuchElementException("heap is empty!");
        }
        int max = data.get(0);
        int lastElement = data.get(data.size() - 1);
        data.set(0,lastElement);
        // 删除最后一个元素
        data.remove(data.size() - 1);
        // 元素下沉
        siftDown(0);
        return max;
    }

    /**
     * 将索引为i的元素进行下沉操作，使其仍然满足最大堆的性质
     * @param i
     */
    private void siftDown(int i) {
        // 当i还有子树时，说明还没判断结束
        // 若左孩子都不存在，一定不存在右孩子
        while (leftChild(i) < data.size()) {
            // 此时仍然存在子树
            int j = leftChild(i);
            // 此时还存在右子树
            if (j + 1 < data.size() && data.get(j + 1) > data.get(j)) {
                // 此时右子树的值大于左子树
                j = j + 1;
            }
            // j一定保存了左右子树的最大值索引
            if (data.get(i) >= data.get(j)) {
                // 此时i对应的元素已经下沉到合适位置
                break;
            }else {
                swap(i,j);
                i = j;
            }
        }
    }

    /**
     * 调整k位置所在的元素，使其仍然满足最大堆的性质
     * @param k
     */
    private void siftUp(int k) {
        // 走到根节点 k == 0
        // 当前节点值 <= 根节点的值
        while (k > 0 && data.get(k) > data.get(parent(k))) {
            // 交换当前位置元素和父节点的元素即可
            int parent = parent(k);
            swap(k,parent);
            k = parent;
        }
    }

    /**
     * 交换当前data数组中k和parent索引的元素
     * @param k
     * @param parent
     */
    private void swap(int k, int parent) {
        int temp = data.get(k);
        data.set(k,data.get(parent));
        data.set(parent,temp);
    }

    /**
     * 根据孩子节点索引k求父节点索引
     * @param k
     * @return
     */
    private int parent(int k) {
        return (k - 1) >> 1;
    }

    /**
     * 根据父节点索引k求左孩子节点下标
     * @param k
     * @return
     */
    private int leftChild(int k) {
        // 2k + 1
        return (k << 1) + 1;
    }

    /**
     * 根据父节点下标求右孩子节点下标
     * @param k
     * @return
     */
    private int rightChild(int k) {
        // 2k + 2
        return (k << 1) + 2;
    }

    @Override
    public String toString() {
        return data.toString();
    }
}